The present invention relates generally to categorizing and matching complex images or patterns, such as fingerprint patterns. In particular, the present invention relates to automatically placing such patterns into predetermined categories for use in matching and identifying the patterns.
The present invention is particularly useful to automatically classify fingerprint patterns into categories to aid in matching such fingerprint patterns. The present invention is discussed herein in the context of a device and method for analyzing fingerprint images. However, those familiar with image processing will recognize that the invention may be applied to analyzing any image.
A fingerprint pattern is the pattern of ridges at the tip of a person's fingers. Each fingerprint is unique. No two individuals have the same fingerprints. Therefore, fingerprints may be used to identify particular individuals by matching fingerprint patterns.
For example, one use of fingerprint matching is to verify the identity of an individual, such as when granting access to a controlled building or area. The individual's fingerprint patterns may be compared against a stored set of fingerprint patterns to verify that the person seeking access is actually the person for whom access has been authorized.
Another use for fingerprint pattern matching is to establish the likely identity of a person who has a particular fingerprint pattern. This use is often employed in criminal investigations. Contact between a person's fingers and an object may leave a replica of the person's fingerprint pattern on the surface of the object. If a fingerprint pattern found on an object can be matched with a fingerprint pattern of a known individual, then it is virtually certain that individual touched the object on which the fingerprint pattern was found.
Thus, when a fingerprint pattern is detected at a location of a crime, the police often want to establish the identity of the person possessing that fingerprint pattern. However, establishing that identity requires comparing the unknown fingerprint with the fingerprints that are already stored on file.
That comparison process is extremely complex and time consuming. There may be a significant number of individuals whose fingerprint patterns are on file. In addition, each finger has its own fingerprint pattern. Therefore, comparing a particular fingerprint pattern with a stored collection of fingerprint patterns may require comparing the unknown fingerprint pattern with up to ten fingerprints in each of potentially millions of stored records.
Because of the value in establishing the identity of a person with a particular fingerprint pattern, and the complexity of the comparison process, various techniques have been developed to attempt to simplify the comparison process.
The earliest simplification was to establish three categories of fingerprint patterns. Each fingerprint pattern can be classified into one of these categories. These categories are based on the appearance of the fingerprint pattern. They are the loop category, the whorl category, and the arch category. Using such categories, the search for an individual possessing a particular fingerprint pattern is somewhat simplified. If the unknown fingerprint pattern is of a whorl type, then only the whorl patterns on file need to be compared. However, with only three categories, there still may be millions of fingerprint patterns on file (reference patterns) to compare with the unknown pattern. This categorization technique remains widely used.
Several techniques for automating the process of comparing fingerprint patterns have been developed. Current techniques compare the fingerprint images directly. Some techniques compare specific features of the fingerprint patterns, such as the minutiae. A fingerprint comprises a pattern of ridges and valleys, and minutiae. Minutiae are the points at the end of the ridges.
One technique for comparing the fingerprint pattern minutiae compares the locations of the minutiae in the X-Y plane of the fingerprint pattern. While this technique is straightforward, a disadvantage of this technique is that the unknown print and the reference print must be carefully aligned for proper comparison. Such alignment may be particularly difficult if the unknown print is only a portion of the complete fingerprint pattern. In addition, this technique is susceptible to errors if the fingerprints being compared were taken under different circumstances. Consider the circumstance when two fingerprint images made by the same finger are being compared. If greater pressure was applied to the finger when making one print than when making the other, the minutiae may be in different places, and the relationship among the minutiae may differ. The minutiae may be spread farther apart in the fingerprint pattern made using greater pressure. Finally, this technique requires that the reference fingerprint image and the unknown fingerprint image be identical in size.
Another technique for comparing minutiae patterns is to compare the relative angles of the ridges associated with the minutiae. This technique lessens errors due to X-Y displacement. However, this technique is rotationally sensitive. Because an unknown fingerprint pattern may be only a partial print, the rotational orientation of the fingerprint pattern may be uncertain. In addition, this technique may be sensitive to changes in minutiae orientation that may arise when the fingerprints being compared were taken under different circumstances.
Yet another technique for comparing minutiae is to compare minutiae within each of several small regions of the fingerprint pattern. By using relatively small areas of the fingerprint, this technique limits the effect of the minutiae spreading when greater pressure is applied to the finger when making the fingerprint. By examining small regions of the fingerprint, the distortions in the fingerprint pattern due to spreading from different finger pressure when making the print are less pronounced. However, the problems of minutiae spreading are not completely eliminated. In addition, this technique is still rotationally sensitive, and the patterns must be aligned to identify the individual regions for comparison.
The above automatic fingerprint matching techniques are directed to matching specific fingerprint patterns. In addition to the difficulties noted above, each of those automatic matching techniques requires a very large amount of computational effort. Such large efforts require large computers and/or substantial time to perform.
Different pattern recognition techniques have been applied to matching other, simpler, types of patterns. For example, techniques have been developed to compare an unknown object with a library of reference patterns. Such techniques have been developed for object recognition systems, for automatically recognizing objects such as trucks, tanks, or particular types of ships or aircraft.
One pattern recognition technique used in connection with such patterns is to use a Fourier image or frequency representation in comparing the image of an unknown object with each of several stored images, each of which corresponds to a particular object. For example, there may be an interest in identifying whether an unknown aircraft is an airplane or a helicopter. The images of one or more known airplanes and one or more known helicopters are stored in a computer. The image of the unknown aircraft is correlated with the stored images to identify the closest fit. This correlation can be accomplished with Fourier transforms, as will be understood by those skilled in the image processing arts.
The pattern recognition technique last described above compares the representations of the objects. The process has proved quite effective when comparing relatively simple patterns, and when comparing a relatively small number of different patterns. However, this technique has not been successfully applied to identifying complex patterns such as fingerprint patterns.
As noted above, fingerprint patterns are extremely complex. Therefore, the calculations involved in correlating such patterns are very complicated, and require a substantial amount of computational capability. In addition, when comparing an unknown fingerprint with fingerprints on file, a very large number of fingerprint patterns must be compared. Therefore, the last described technique becomes difficult and time consuming for comparing an unknown fingerprint pattern with fingerprint patterns on file.
It is an object of the present invention to simplify the process of matching an unknown fingerprint to a database of fingerprint patterns.
It is an object of the present invention to reduce the number of stored fingerprint patterns with which a detailed comparison of an unknown fingerprint must be made.
It is an object of the present invention to automatically classify complex patterns, such as fingerprint patterns, into predetermined categories.
It is an object of the present invention to automatically classify fingerprint patterns into appropriate ones of a large number of categories of fingerprint patterns.
It is an object of the present invention to automatically classify fingerprint patterns regardless of the spatial alignment of the fingerprint.
It is an object of the present invention to automatically classify fingerprint patterns regardless of the angular orientation of the fingerprint.
It is an object of the present invention to automatically classify fingerprint patterns regardless of the size of the fingerprint.